<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- 比赛的冠亚季军（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>有N&#xff08;3 ≤ N &lt; 10000&#xff09;个运动员&#xff0c;他们的id为0到N-1,他们的实力由一组整数表示。他们之间进行比赛&#xff0c;需要决出冠亚军。比赛的规则是0号和1号比赛&#xff0c;2号和3号比赛&#xff0c;以此类推&#xff0c;每一轮&#xff0c;相邻的运动员进行比赛&#xff0c;获胜的进入下一轮&#xff1b;实力值大的获胜&#xff0c;实力值相等的情况&#xff0c;id小的情况下获胜&#xff1b;轮空的直接进入下一轮。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入一行N个数字代表N的运动员的实力值(0&lt;&#61;实力值&lt;&#61;10000000000)。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出冠亚季军的id&#xff0c;用空格隔开。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">2 3 4 5</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">3 1 2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>第一轮比赛&#xff0c;</p> <p>id为0实力值为2的运动员和id为1实力值为3的运动员比赛&#xff0c;1号胜出进入下一轮争夺冠亚军&#xff0c;</p> <p>id为2的运动员和id为3的运动员比赛&#xff0c;3号胜出进入下一轮争夺冠亚军&#xff0c;</p> <p>冠亚军比赛&#xff0c;3号胜1号&#xff0c;</p> <p>故冠军为3号&#xff0c;亚军为1号&#xff0c;2号与0号&#xff0c;比赛进行季军的争夺&#xff0c;2号实力值为4&#xff0c;0号实力值2&#xff0c;故2号胜出&#xff0c;得季军。冠亚季军为3 1 2。</p> </td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题主要考察逻辑分析。</p> 
<p></p> 
<p>每轮晋级赛&#xff0c;都会将人数砍一半&#xff0c;因此本题不怕大数量级。</p> 
<p>在每轮晋级赛中&#xff0c;相邻的运动员组队进行比赛&#xff0c;比如有实力数组&#xff1a;[0,1,2,3,4,5,6,7,8]</p> 
<p>其中0,1比赛&#xff0c;2,3比赛&#xff0c;4,5比赛&#xff0c;6,7比赛&#xff0c;其中实力值较大者晋级去竞争冠军组&#xff0c;对于8而言&#xff0c;没有对手&#xff0c;按照题目意思是直接晋级。</p> 
<p>按照上面逻辑&#xff0c;得到获胜组为&#xff1a;[1,3,5,7,8]&#xff0c;失败组为&#xff1a;[0,2,4,6]</p> 
<p>我们可以创建一个链表用于保存每轮的获胜组和失败组&#xff0c;但是需要保证获胜组在头部</p> 
<p>即可得 [1,3,5,7,8] -&gt; [0,2,4,6]</p> 
<p></p> 
<p>接下来取出链表头部组[1,3,5,7,8]&#xff0c;继续进行晋级赛&#xff1a;</p> 
<p>其中1,3比赛&#xff0c;5,7比赛&#xff0c;8没有对手直接晋级&#xff0c;</p> 
<p>最后得到获胜组[3,7,8]&#xff0c;失败组[1,5]&#xff0c;将它们压入链表头部</p> 
<p>[3,7,8] -&gt; [1,5] -&gt; [0,2,4,6]</p> 
<p></p> 
<p>接下来取出链表头部组[3,7,8] &#xff0c;继续进行晋级赛&#xff1a;</p> 
<p>其中3,7比赛&#xff0c;8没有对手直接晋级&#xff0c;</p> 
<p>最后得到获胜组[7,8]&#xff0c;失败组[3]&#xff0c;将它们压入链表头部</p> 
<p>[7,8] -&gt; [3] -&gt; [1,5] -&gt; [0,2,4,6]</p> 
<p></p> 
<p>此时链表长度超过了3&#xff0c;因此链表尾部的组失去了竞争季军的资格&#xff0c;因此弹出尾部</p> 
<p>[7,8] -&gt; [3] -&gt; [1,5]</p> 
<p>而链表头部组的运动员个数还不为1&#xff0c;即还有多个人竞争冠军</p> 
<p></p> 
<p>因此&#xff0c;继续取出链表头部组[7,8]&#xff0c;进行晋级赛&#xff1a;</p> 
<p>其中7,8比赛&#xff0c;</p> 
<p>最后得到获胜组[8]&#xff0c;失败组[7]&#xff0c;将它们压入链表头部</p> 
<p>[8] -&gt; [7] -&gt; [3] -&gt; [1,5]</p> 
<p></p> 
<p>此时链表长度超过了3&#xff0c;因此链表尾部的组失去了竞争季军的资格&#xff0c;因此弹出尾部</p> 
<p>[8] -&gt; [7] -&gt; [3]</p> 
<p>最后的冠军实力值8&#xff0c;亚军实力值7&#xff0c;季军实力值3</p> 
<p>但是题目最后要求输出的是运动员的id&#xff0c;因此我们在一开始的时候可以定义一个运动员类&#xff0c;属性有运动员的id和运动员的实力。</p> 
<p>这样最后输出就可以获取到运动员id了。</p> 
<p></p> 
<p>这里还有一个需要注意的点是&#xff1a;</p> 
<p>最后一轮晋级赛&#xff0c;必然只有两个人&#xff0c;即分出冠军和亚军</p> 
<p>倒数第二轮晋级赛&#xff0c;只可能是4人&#xff0c;或者3人&#xff0c;如下图所示</p> 
<p><img alt="" height="267" src="https://img-blog.csdnimg.cn/b2166321fc564678813df76526cb04e5.png" width="403" /></p> 
<p> <img alt="" height="301" src="https://img-blog.csdnimg.cn/b14573f4c48546a2a26ec26e9a9ef722.png" width="428" /></p> 
<p> 如果倒数第二轮晋级赛有五人的话&#xff0c;是无法在下轮中产生冠军和亚军的</p> 
<p><img alt="" height="290" src="https://img-blog.csdnimg.cn/eb622c90264944dd8d953b1bbe110412.png" width="503" /></p> 
<p></p> 
<p>因此&#xff0c;季军争夺组只会有2人或者1人&#xff0c;因为&#xff0c;如下图&#xff0c;倒数第二轮晋级赛的失败者只有两人或者一人</p> 
<p><img alt="" height="292" src="https://img-blog.csdnimg.cn/9b60db3cd85e487fac557c6338f27577.png" width="446" /></p> 
<p><img alt="" height="307" src="https://img-blog.csdnimg.cn/e73c9273a0184d759826036499b29b16.png" width="365" /></p> 
<p>因此&#xff0c;前面定义的链表&#xff0c;最终的形态下&#xff1a;</p> 
<p>第一个节点只有一个运动员&#xff08;冠军&#xff09;&#xff0c;第二个节点只有一个运动员&#xff08;亚军&#xff09;&#xff0c;第三个节点可能有一个&#xff0c;也可能有两个&#xff08;季军争夺&#xff09;</p> 
<p>因此针对第三个节点&#xff0c;需要进行季军争夺&#xff0c;直接进行排序取第一个人即可&#xff0c;排序逻辑&#xff1a;</p> 
<ul><li>实力值大的获胜&#xff0c;如果实力值相同&#xff0c;则id小的获胜</li></ul> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 运动员类
  static class Sport {
    int id; // 运动员的id
    long strength; // 运动员的实力

    public Sport(int id, long strength) {
      this.id &#61; id;
      this.strength &#61; strength;
    }
  }

  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    long[] strengths &#61; Arrays.stream(sc.nextLine().split(&#34; &#34;)).mapToLong(Long::parseLong).toArray();

    System.out.println(getResult(strengths));
  }

  public static String getResult(long[] strength) {
    // ans只记录三个组&#xff0c;冠军组&#xff0c;亚军组&#xff0c;季军组
    LinkedList&lt;ArrayList&lt;Sport&gt;&gt; ans &#61; new LinkedList&lt;&gt;();

    // 将输入的实力值&#xff0c;转化为运动员集合
    ArrayList&lt;Sport&gt; sports &#61; new ArrayList&lt;&gt;();
    for (int i &#61; 0; i &lt; strength.length; i&#43;&#43;) sports.add(new Sport(i, strength[i]));

    // 晋级赛
    promote(sports, ans);

    // 冠军组如果不是一个人&#xff0c;那么还需要取出冠军组继续进行晋级赛
    while (ans.getFirst().size() &gt; 1) {
      promote(ans.removeFirst(), ans);
    }

    // 冠军
    int first &#61; ans.get(0).get(0).id;

    // 亚军
    int second &#61; ans.get(1).get(0).id;

    // 季军
    ans.get(2)
        .sort(
            (a, b) -&gt;
                a.strength !&#61; b.strength ? b.strength - a.strength &gt; 0 ? 1 : -1 : a.id - b.id);
    int third &#61; ans.get(2).get(0).id;

    return first &#43; &#34; &#34; &#43; second &#43; &#34; &#34; &#43; third;
  }

  public static void promote(ArrayList&lt;Sport&gt; sports, LinkedList&lt;ArrayList&lt;Sport&gt;&gt; ans) {
    // 记录获胜组
    ArrayList&lt;Sport&gt; win &#61; new ArrayList&lt;&gt;();
    // 记录失败组
    ArrayList&lt;Sport&gt; fail &#61; new ArrayList&lt;&gt;();

    for (int i &#61; 1; i &lt; sports.size(); i &#43;&#61; 2) {
      // 序号大的运动员
      Sport major &#61; sports.get(i);
      // 序号小的运动员
      Sport minor &#61; sports.get(i - 1);

      if (major.strength &gt; minor.strength) {
        win.add(major);
        fail.add(minor);
      } else {
        // 如果序号大的运动员的实力 &lt;&#61; 序号小的运动员&#xff0c;则序号小的运动员获胜
        win.add(minor);
        fail.add(major);
      }
    }

    // 如果晋级赛中运动员个数是奇数个&#xff0c;那么最后一个运动员直接晋级
    if (sports.size() % 2 !&#61; 0) {
      win.add(sports.get(sports.size() - 1));
    }

    // 依次头部压入失败组&#xff0c;获胜组&#xff0c;保证头部是获胜组
    ans.addFirst(fail);
    ans.addFirst(win);

    // 如果保留组个数超过3个&#xff0c;那么需要将超过部分的组去掉&#xff0c;因为这部分人已经无缘季军
    while (ans.size() &gt; 3) ans.removeLast();
  }
}
</code></pre> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  const sports &#61; line
    .split(&#34; &#34;)
    .map(Number)
    .map((val, idx) &#61;&gt; new Sport(idx, val));

  console.log(getResult(sports));
});

function getResult(sports) {
  // ans只记录三个组&#xff0c;依次是&#xff1a;冠军组&#xff0c;亚军组&#xff0c;季军组
  const ans &#61; [];

  // 晋级赛
  promote(sports, ans);

  // 冠军组如果不是一个人&#xff0c;那么还需要取出冠军组继续进行晋级赛
  while (ans[0].length &gt; 1) {
    promote(ans.shift(), ans);
  }

  // 冠军
  const first &#61; ans[0][0].id;
  // 亚军
  const second &#61; ans[1][0].id;

  // 季军
  ans[2].sort((a, b) &#61;&gt;
    a.strength !&#61; b.strength ? b.strength - a.strength : a.id - b.id
  );
  const third &#61; ans[2][0].id;

  return &#96;${first} ${second} ${third}&#96;;
}

function promote(sports, ans) {
  // 记录获胜组
  const win &#61; [];
  // 记录失败组
  const fail &#61; [];

  for (let i &#61; 1; i &lt; sports.length; i &#43;&#61; 2) {
    // 序号大的运动员
    const major &#61; sports[i];
    // 序号小的运动员
    const minor &#61; sports[i - 1];

    if (major.strength &gt; minor.strength) {
      win.push(major);
      fail.push(minor);
    } else {
      // 如果序号大的运动员的实力 &lt;&#61; 序号小的运动员&#xff0c;则序号小的运动员获胜
      win.push(minor);
      fail.push(major);
    }
  }

  // 如果晋级赛中运动员个数是奇数个&#xff0c;那么最后一个运动员直接晋级
  if (sports.length % 2 !&#61; 0) {
    win.push(sports.at(-1));
  }

  // 依次头部压入失败组&#xff0c;获胜组&#xff0c;保证头部是获胜组
  ans.unshift(fail);
  ans.unshift(win);

  // 如果保留组个数超过3个&#xff0c;那么需要将超过部分的组去掉&#xff0c;因为这部分人已经无缘季军
  while (ans.length &gt; 3) ans.pop();
}

class Sport {
  constructor(id, strength) {
    this.id &#61; id; // 运动员的id
    this.strength &#61; strength; // 运动员的实力
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
tmp &#61; list(map(int, input().split()))


class Sport:
    def __init__(self, idx, strength):
        self.idx &#61; idx  # 运动员的id
        self.strength &#61; strength    # 运动员的实力


# 将输入的实力值&#xff0c;转化为运动员集合
sports &#61; []
for i in range(len(tmp)):
    sports.append(Sport(i, tmp[i]))


def promote(sports, ans):
    # 记录获胜组
    win &#61; []
    # 记录失败组
    fail &#61; []

    for i in range(1, len(sports), 2):
        # 序号大的运动员
        major &#61; sports[i]
        # 序号小的运动员
        minor &#61; sports[i-1]

        if major.strength &gt; minor.strength:
            win.append(major)
            fail.append(minor)
        else:
            # 如果序号大的运动员的实力 &lt;&#61; 序号小的运动员&#xff0c;则序号小的运动员获胜
            win.append(minor)
            fail.append(major)

    # 如果晋级赛中运动员个数是奇数个&#xff0c;那么最后一个运动员直接晋级
    if len(sports) % 2 !&#61; 0:
        win.append(sports[-1])

    # 依次头部压入失败组&#xff0c;获胜组&#xff0c;保证头部是获胜组
    ans.insert(0, fail)
    ans.insert(0, win)

    # 如果保留组个数超过3个&#xff0c;那么需要将超过部分的组去掉&#xff0c;因为这部分人已经无缘季军
    while len(ans) &gt; 3:
        ans.pop()


# 算法入口
def getResult():
    # ans只记录三个组&#xff0c;冠军组&#xff0c;亚军组&#xff0c;季军组
    ans &#61; []

    # 晋级赛
    promote(sports, ans)

    # 冠军组如果不是一个人&#xff0c;那么还需要取出冠军组继续进行晋级赛
    while len(ans[0]) &gt; 1:
        promote(ans.pop(0), ans)

    # 冠军
    first &#61; ans[0][0].idx

    # 亚军
    second &#61; ans[1][0].idx

    # 季军
    ans[2].sort(key&#61;lambda x: (-x.strength, x.idx))
    third &#61; ans[2][0].idx

    return f&#34;{first} {second} {third}&#34;


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>